package selectionSort;

import javax.print.DocFlavor;
import java.util.Arrays;

/**
 * 选择排序类。
 */
public class SelectionSort {
    public SelectionSort() {
    }

    /**
     * 最初实现的需要额外空间的版本。
     * @param data
     * @return
     */
    public static Integer[] sort_extraSpace(Integer[] data) {
        //需要额外的空间版本
        Integer[] tmp = new Integer[data.length];
        for (int i = 0; i < data.length; i++) {
            int min = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[min]) {
                    min = j;
                }
            }
            tmp[i] = data[min];
            int k = data[min];
            data[min] = data[i];
            data[i] = k;
        }
        return tmp;
    }

    /**
     * 迭代版接口
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] data) {
        /**
         * 不需要额外空间版本。
         */
        for (int i = 0; i < data.length - 1; i++) {
            //循环不变量：[0,i)已排序；[i,n)未排序。
            int min = i;
            //选择[i,n)中最小值索引。
            for (int j = i + 1; j < data.length; j++)
                if (data[j].compareTo(data[min]) < 0)
                    min = j;
            swap(data, min, i);
        }
    }

    /**
     * 交换data[i]和data[j]。
     * @param data
     * @param i
     * @param j
     * @param <E>
     */
    public static <E> void swap(E[] data, int i, int j) {
        E k = data[i];
        data[i] = data[j];
        data[j] = k;
    }

    /**
     * 递归排序接口
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sortRecursive(E[] data) {
        sortRecursiveHelper(data,0,data.length-1);
    }

    /**
     * 递归实现选择排序。出口和选择排序类似。每一次找出最小的一个放到data[l]处，然后递归调用。
     * @param data
     * @param l
     * @param r
     * @param <E>
     */
    private static <E extends Comparable<E>> void sortRecursiveHelper(E[] data, int l, int r) {
        if (data == null || r - l + 1 <= 1)
            return;
        int minIndex = l;
        for (int i = l + 1; i <= r; i++) {
            if (data[i].compareTo(data[minIndex]) < 0)
                minIndex = i;
        }
        swap(data, minIndex, l);
        sortRecursiveHelper(data,l+1,r);
    }

    public static void main(String[] args) {
        int[] dataSize = {100, 1000};
        for (int n : dataSize) {
            Integer[] data = ArrayGenerator.generateRandomArray(n, n);
            Integer[] data2 = Arrays.copyOf(data,data.length);
            SortingHelper.sortTest("SelectionSort", data);
            SortingHelper.sortTest("SelectionSortR",data2);
        }
    }
}
